Path sum IV [Topological Sort]

Time: O(N); Space: O(P); medium

If the depth of a tree is smaller than 5, then this tree can be represented by a list of three-digits integers.

For each integer in this list: 1. The hundreds digit represents the depth D of this node, 1 <= D <= 4. 2. The tens digit represents the position P of this node in the level it belongs to, 1 <= P <= 8. The position is the same as that in a full binary tree. 3. The units digit represents the value V of this node, 0 <= V <= 9.

Given a list of ascending three-digits integers representing a binary with the depth smaller than 5. You need to return the sum of all paths from the root towards the leaves.

Example 1:

Input: nums = [113, 215, 221]

Output: 12

Explanation:

  • The tree that the list represents is:

      3
 / \
5   1

The path sum is (3 + 5) + (3 + 1) = 12.

Example 2:

Input: nums = [113, 221]

Output: 4

Explanation:

  • The tree that the list represents is:

    3
 \
  1

The path sum is (3 + 1) = 4.

[4]:

import collections

class Solution1(object):
    def pathSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        class Node(object):
            def __init__(self, num):
                self.level = num//100 - 1
                self.i = (num % 100)//10 - 1
                self.val = num % 10
                self.leaf = True

            def isParent(self, other):
                return self.level == other.level-1 and \
                       self.i == other.i//2

        if not nums:
            return 0
        result = 0
        q = collections.deque()
        dummy = Node(10)
        parent = dummy

        for num in nums:
            child = Node(num)
            while not parent.isParent(child):
                result += parent.val if parent.leaf else 0
                parent = q.popleft()
            parent.leaf = False
            child.val += parent.val
            q.append(child)

        while q:
            result += q.pop().val

        return result

[5]:

s = Solution1()
nums = [113, 215, 221]
assert s.pathSum(nums) == 12
nums = [113, 221]
assert s.pathSum(nums) == 4